public class BinarySearchTree {
    public static void main(String[] args) {
        BinarySearchTree test = new BinarySearchTree();
        int[] array = new int[]{9,12,45,3,6,14,7};
        for(int i = 0; i < array.length; i++) {
            test.insert(array[i]);
        }
        System.out.println(test.search(14));
        System.out.println(test.search(141));
    }

    // 1 定义节点内部类
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    private TreeNode root;

    // 2 插入方法
    public boolean insert(int key) {
        /**
         * 插入*/
        // 1 判断根节点是否为空
        if (this.root == null) {
            this.root = new TreeNode(key);
            return true;
        }
        // 2
        TreeNode cur = this.root;
        TreeNode parent = null;
        while (cur != null) {
            if (key < cur.val) {
                parent = cur;
                cur = cur.left;
            } else if (key > cur.val) {
                parent = cur;
                cur = cur.right;
            } else {
                // 相等
                return false;
            }
        }
        // 3 判断key与上一个节点值的大小，以确定是插在左子树还是右子树
        if(key > parent.val) {
            parent.right = new TreeNode(key);
        } else {
            parent.left = new TreeNode(key);
        }
        return true;
    }

    // 3 排序
    public boolean search(int key) {
        /**
         * 搜索*/
        // 1 遍历
        TreeNode cur = this.root;
        while(cur != null) {
            if(key > cur.val) {
                cur = cur.right;
            } else if(key < cur.val) {
                cur = cur.left;
            } else {
                return true;
            }
        }
        return false;
    }
}
